package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 2122. 还原原数组
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/2 16:55
 */
public class RecoverArray {


    public static void main(String[] args) {
        RecoverArray test = new RecoverArray();


        // [3,7,11]
//        int[] nums = {2, 10, 6, 4, 8, 12};

        // [2,2]
//        int[] nums = {1, 1, 3, 3};

        // [220]
//        int[] nums = {5, 435};

        // [71,89,92,93,93,100,101,106,115,129]
        int[] nums = {150, 156, 143, 142, 151, 143, 139, 179, 121, 165, 50, 56, 43, 42, 51, 43, 39, 79, 21, 65};

//        int length = 10;
//        int max = 100;
//        int[] arr1 = Utils.getArr(length, 0, max);
//        int[] arr2 = Utils.getArr(length, 0, max);
//        for (int i = 0; i < length; i++) {
//            arr1[i] = arr2[i] + max;
//        }
//        int[] nums = new int[length << 1];
//        for (int i = 0; i < length; i++) {
//            nums[i] = arr1[i];
//        }
//        for (int i = 0; i < length; i++) {
//            nums[i + length] = arr2[i];
//        }
//        System.out.println();
//        System.out.println(Arrays.toString(nums));

        int[] ints = test.recoverArray(nums);
        System.out.println(Arrays.toString(ints));

    }

    public int[] recoverArray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, (a, b) -> a + b);
        }
        int length = nums.length;
        int l = length >> 1;
        int[] arr = new int[l];
        Arrays.sort(nums);
        int item = nums[0];
        for (int i = 1; i < length; i++) {
            int f = nums[i];
            if (f == item || ((f - item) & 1) != 0) {
                continue;
            }
            int t = (f - item);
            int t1 = t >> 1;
            Map<Integer, Integer> m = new HashMap<>(map);
            int c = 1;
            m.put(f, m.get(f) - 1);
            arr[0] = nums[0] + t1;
            for (int j = 1; j < length; j++) {
                Integer count1 = m.get(nums[j]);
                if (count1 == null || count1 == 0) {
                    continue;
                }
                int v = nums[j] + t;
                Integer count2 = m.get(v);
                if (count2 == null || count2 == 0) {
                    break;
                }
                m.put(nums[j], count1 - 1);
                m.put(v, count2 - 1);
                arr[c] = nums[j] + t1;
                c++;
                if (c == l) {
                    return arr;
                }
            }
        }
        return arr;
    }
}
